package com.example.question.dp.dp1;

/**
 * 这个题目  递归和动态规划都试试
 */
public class Code10_1143 {

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return 0;
        }
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        // 定义数组
        int[][] dp = new int[chars1.length][chars2.length];
        // 初始化边界值
        for (int row = 0; row < chars1.length; row++) {
            if (chars1[row] == chars2[0] || (row >= 1 && dp[row - 1][0] == 1)) {
                dp[row][0] = 1;
            } else {
                dp[row][0] = 0;
            }
        }

        for (int col = 1; col < chars2.length; col++) {
            if (chars2[col] == chars1[0] || dp[0][col - 1] == 1) {
                dp[0][col] = 1;
            } else {
                dp[0][col] = 0;
            }
        }
        // 填充数组
        for (int row = 1; row < chars1.length; row++) {
            for (int col = 1; col < chars2.length; col++) {
                if (chars1[row] == chars2[col]) {
                    dp[row][col] = dp[row - 1][col - 1] + 1;
                } else {
                    dp[row][col] = Math.max(dp[row - 1][col], dp[row][col - 1]);
                }
            }
        }
        // 返回结果
        return dp[chars1.length - 1][chars2.length - 1];
    }
}
